package leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 参考递归序，使用栈模拟系统压栈
 * <p>
 * leetcode:
 * 144. 二叉树的前序遍历
 * 94. 二叉树的中序遍历
 * 145. 二叉树的后序遍历
 */
public class BinaryTreeTraversal {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        class Node {
            TreeNode treeNode;
            int flag;

            public Node(TreeNode treeNode, int flag) {
                this.treeNode = treeNode;
                this.flag = flag;
            }
        }

        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> ans = new ArrayList<>();
            if (root == null) return ans;
            Stack<Node> stack = new Stack<>();
            stack.push(new Node(root, 1));
            while (!stack.isEmpty()) {
                Node cur = stack.pop();
                ans.add(cur.treeNode.val);
                if (cur.treeNode.right != null) stack.push(new Node(cur.treeNode.right, 1));
                if (cur.treeNode.left != null) stack.push(new Node(cur.treeNode.left, 1));
            }
            return ans;
        }

        /**
         * 根据 preorderTraversal 可知，无需 flag
         */
        public List<Integer> preorderTraversal2(TreeNode root) {
            List<Integer> ans = new ArrayList<>();
            if (root == null) return ans;
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                TreeNode cur = stack.pop();
                ans.add(cur.val);
                if (cur.right != null) stack.push(cur.right);
                if (cur.left != null) stack.push(cur.left);
            }
            return ans;
        }

        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> ans = new ArrayList<>();
            if (root == null) return ans;
            Stack<Node> stack = new Stack<>();
            stack.push(new Node(root, 1));
            while (!stack.isEmpty()) {
                Node cur = stack.pop();
                if (cur.flag == 1) {
                    stack.push(new Node(cur.treeNode, 2));
                    if (cur.treeNode.right != null) stack.push(new Node(cur.treeNode.right, 1));
                    if (cur.treeNode.left != null) stack.push(new Node(cur.treeNode.left, 1));
                } else {
                    ans.add(cur.treeNode.val);
                }
            }
            return ans;
        }

        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> ans = new ArrayList<>();
            if (root == null) return ans;
            Stack<Node> stack = new Stack<>();
            stack.push(new Node(root, 1));
            while (!stack.isEmpty()) {
                Node cur = stack.pop();
                if (cur.flag == 1) {
                    if (cur.treeNode.right != null) stack.push(new Node(cur.treeNode.right, 1));
                    stack.push(new Node(cur.treeNode, 2));
                    if (cur.treeNode.left != null) stack.push(new Node(cur.treeNode.left, 1));
                } else {
                    ans.add(cur.treeNode.val);
                }
            }
            return ans;
        }
    }
}
